10004 - Bicoloring/10004.2.cpp

   1 /*
   2   Problem: 10004 - Bicoloring (UVa online judge)
   3
   4   Author: Andrés Mejía-Posada (http://github.com/andmej/acm)
   5   Algorithm: Depth-first search
   6  */
   7 #include <iostream>
   8 #include <vector>
   9
  10 using namespace std;
  11
  12 bool dfs(int u, int c, int * color, vector<int> * g){
  13   //printf("u = %d, c = %d, color[%d] = %d\n", u, c, u, color[u]);
  14   if (color[u] != 0) return (c == color[u]);
  15
  16   color[u] = c;
  17   for (int i=0; i<g[u].size(); ++i){
  18     int nc = (c == 1 ? 2 : 1);
  19     if (dfs(g[u][i], nc, color, g) == false){
  20       return false;
  21     }
  22   }
  23   return true;
  24 }
  25
  26 int main(){
  27   int n, l;
  28   while (cin >> n && n){
  29     cin >> l;
  30     vector<int> g[n];
  31     int color[n];
  32     memset(color, 0, sizeof color);
  33
  34     while (l--){
  35       int u, v;
  36       cin >> u >> v;
  37       g[u].push_back(v);
  38       g[v].push_back(u);
  39     }
  40
  41     cout << (dfs(0, 1, color, g) ? "" : "NOT ") << "BICOLORABLE." << endl;
  42   }
  43   return 0;
  44 }